\documentclass[10pt,a4paper]{report}
\usepackage{ifpdf}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage[top=2.5cm,right=2.5cm,bottom=2.5cm,left=2.5cm]{geometry}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{lscape}
\usepackage{pstricks, pst-node, pst-tree}

\parindent 1.0cm

\title{Rapport utilisation avancée des arbres}

\author{Julien Durillon \and Clotilde Massot}

\date{\today}

\ifpdf
\pdfinfo {
	/Author (Julien Durillon Clotilde Massot)
	/Title (Rapport utilisation avancée des arbres)
	/Subject (Rapport utilisation avancée des arbres)
	/Keywords (rapport, structures, algorithmique, germann)
	/CreationDate (D:20091202161611)
}

\fi
\begin{document}
	\maketitle

	\tableofcontents\newpage

	\chapter{Étude du sujet et modélisation}
		\section{Étude du sujet}

			\subsection{Objectif}
				L'objectif du projet est de créer une application permettant d'optimiser des images PNG grâce à des opérations sur les pixels, les régions, et les couleurs en elles-mêmes.

				Nous devons pour cela utiliser des structures d'arbres d'arité 4 et 8.

			\subsection{Besoins}
				Une bibliothèque permettant de gérer des arbres d'arités diverses. Nous avons besoin des opérations suivantes :
				\begin{itemize}
					\item Création d'un arbre.
					\item Ajout d'un élément à une position donnée en tant que fils d'un autre.
					\item Suppression d'un nœud et de ses enfants.
					\item Stockage d'un objet dans un nœud.
					\item Possibilité d'accès à un élément à partir de son père, de son étiquette, ou de ses fils.
				\end{itemize}


				Par chance, nous possédons une telle bibliothèque, créée lors de la première partie de ce projet, à laquelle il ne manque que la suppression d'un nœud.

				Il nous faut aussi des méthodes de chargement et d'écriture d'image au format PNG. Cela nous est fourni.

		\section{Modélisation de l'application}
			\subsection{Cas d'utilisation}

				Les différents cas d'utilisation du logiciel sont représentés en Figure \ref{fig:1} :
%%				\begin{figure}[!ht]
				\begin{center}
					\includegraphics[width=8cm,height=7cm]{images/use_case.eps}
					\captionof{figure}{\label{fig:1}Cas d'utilisation}

				\end{center}
	%%			\end{figure}

				Un utilisateur peut importer et exporter une image au format PNG, modifier les couleurs en opérant à des modifications de la palette de couleurs, ou des régions de l'image. On peut aussi modifier la compression en choisissant une métrique plus ou moins grande pour les fusions de régions.

			\subsection{Diagrammes de classe}

				Les classes utilisées dans ce projet s'agencent comme décrit dans la Figure \ref{fig:classes} :

				\begin{landscape}
					\begin{figure}[ht]
						\begin{center}
							\vspace{-0.5cm}\hspace{0.5cm}\fbox{\includegraphics[width=23cm,height=15cm]{images/classes.eps}}
						\end{center}
						\caption{Diagramme de Classes}
						\label{fig:classes}

					\end{figure}
				\end{landscape}


			\subsection{Classes}

				Pour plus d'information sur les méthodes des classes présentées ci-dessous, voir la documentation fournie.

				\subsubsection{ArbreTM, ArbreLA et Noeud}

					Ces classes ont été décrites dans la première partie du projet. Nous avons dû ajouter quelques fonctionnalités, non précisées dans la première partie du projet.

					Nous avons donc principalement rajouté le stockage d'un objet dans les nœuds de l'arbre, ainsi que la méthode deleteNoeud(Nœud n), qui prend en paramètre un nœud, et le supprime de l'arbre, ainsi que toute l'arborescence qui en découle.

					L'utilisation de notre bibliothèque nous a permis de corriger quelques bugs que nous n'avions pas découverts.

				\subsubsection{QuadTree}
					Cette classe définit un ArbreTM d'arité 4 paramétré par la classe Color du package \emph{java.awt}. Ce n'est rien de plus qu'un alias. Nous avons choisi l'implémentation ArbreTM, car l'arbre généré est quasiment complet. On ne perd donc pas de mémoire, et on a un accès plus rapide aux éléments.

				\subsubsection{QuadTreeManager}
					Cette classe permet comme son nom l'indique de gérer des opérations sur un QuadTree. On y trouve les opérations d'import/export d'image, de fusion de régions, et autres opérations proposées par le sujet.

				\subsubsection{OcTree}
					Représente un ArbreLA d'arité 8, paramétré par la classe OcTreeElement. L'implémentation ArbreLA a été choisie pour économiser de la place, car l'arbre n'est jamais vraiment rempli, et on aurait beaucoup de perte de place en utilisant une implémentation plus statique.

				\subsubsection{OcTreeElement}
					Représente un couple (Color,int) contenant une couleur et son nombre d'occurrences dans l'image. On peut les comparer, auquel cas, la relation d'ordre > correspond à la relation d'ordre sur le nombre d'occurrences.

				\subsubsection{OcTreeManager}
					Gère un OcTree. Plusieurs opérations sont disponibles : importer une palette, exporter une couleur, réduire la palette. Les opérations sont disponibles depuis n'importe où, mais l'export d'une couleur est surtout utilisé par QuadTree lors de l'export de l'image.

				\subsubsection{ColorEditor}
					Cette classe offre des opérations sur les couleurs, telles que la moyenne de 2 ou de 4 couleurs, la distance entre 2 ou 4 couleurs, fixer la métrique utilisée pour déterminer si deux couleurs sont proches ou non.

	\chapter{Implémentations}

		\section{QuadTreeManager}
			\subsection{Méthodes d'import}

				\subsubsection{addPixel}
					Cette méthode ajoute un pixel à l'arbre, en créant ses parents si besoin. L'algorithme est assez trivial, et suit les indications du sujet : en prenant le bit de poids fort, dans l'abscisse et l'ordonnée, et on les concatène pour trouver la position à laquelle passer.\footnote{Note : À cause de l'implémentation des arbres, les positions des fils sont comprises entre 1 et n. Il faut donc faire +1 à chaque insertion.} Si le fils n'existe pas, on le crée puis on calcule (grâce aux bits suivants) auquel de ses fils il faut passer. Une fois en bas, on crée le nœud feuille, et on y stocke la couleur.

					Cette fonction coûte le prix d'un parcours de la racine à une feuille, soit un $O(log (n))$

				\subsubsection{importBitMapTable}
					Celle-ci appelle addPixel pour chaque pixel. Elle initialise aussi les dimensions de l'image et la profondeur de l'arbre initial pour pouvoir reconstruire l'image dans des conditions identiques à l'image de départ.
					Le coût temporel de cette fonction est en $O(n\times log (n))$.

			\subsection{Méthodes d'export}

				\subsubsection{boutDeTableau}
					Cette méthode prend en paramètre un nœud et une profondeur, et ressort un tableau de Color. C'est une fonction récursive. On y trouve plusieurs cas :

					\begin{itemize}
						\item Si le nœud contient une couleur et correspond à un pixel, on ressort un tableau à deux dimensions et une case, contenant la couleur, récupérée dans l'Octree\footnote{Ceci est expliqué dans la section sur Octree}.
						\item Si le nœud contient une couleur, et correspond à une région, on ressort un tableau à deux dimensions, contenant tous les pixels de la région, tous de la même couleur.
						\item Si le nœud est null, on renvoie null.
						\item Enfin, si le nœud ne contient pas de couleur, on rappelle la fonction boutDeTableau sur chacun des quatre fils, puis on assemble les tableaux ainsi créés.
					\end{itemize}

					Cette méthode a un coup temporel en $O(n)$.

				\subsubsection{exportBitMapTable}
					Cette méthode ne fait qu'appeler la méthode boutDeTable, et en ressort le résultat.

			\subsection{Méthodes de compression}

					\subsubsection{fusionnable}
						Cette méthode prend un nœud en paramètre, et retourne un booléen si ses fils sont fusionnables, i.e. que leurs couleurs sont suffisamment proches\footnote{cf. les méthodes de ColorEditor}. Cette opération s'effectue en $O(1)$.

					\subsubsection{fusionNoeud}
						Cette méthode prend un nœud, et fusionne ses fils, s'ils sont fusionnables. On appelle donc moyenne4Colors pour calculer la couleur moyenne, on supprime le nœud, et on le remplace par un contenant la nouvelle couleur. Cette opération s'effectue en $O(1)$.

					\subsubsection{compresse}
						Parcourt l'arbre et fusionne les nœuds fusionnables, jusqu'à ce que plus rien ne soit fusionnable. Elle se déroule comme ceci :

						On parcourt l'arbre, et on stocke les nœuds fusionnables dans une liste. Ensuite on fusionne chaque élément de la liste, puis on recommence le tout, tant que l'on a un parcours "améliorant". Cette opération se fait donc en $O(n)$, car l'opération la plus longue est le parcours de chaque élément de l'arbre.

	\section{OcTreeManager}
		\subsection{Méthodes d'import}

				\subsubsection{addCouleur}
					Cette méthode fonctionne de la même manière que pour l'ajout d'un pixel dans le QuadTree : créer l'arborescence petit à petit, en ajoutant les nœuds au fur et à mesure des besoins. Cependant, l'OcTree comprend en plus le nombre d'occurrences de chaque couleur ajoutée. Donc quand, dans l'ajout d'une couleur, on tombe sur une couleur déjà créée, on incrémente simplement le nombre d'occurrences de celle-ci.

				\subsubsection{importPaletteImage}
					Celle-ci ne fait que appeler addCouleur pour chaque pixel de l'image.

		\subsection{Méthodes d'export}
				\subsubsection{recupererCouleur}
					Cette méthode prend un Color en paramètre, et renvoie la couleur trouvée dans l'OcTree, qu'elle ait été modifiée ou non.
					On fait donc un parcours de l'arbre de la même manière que dans addCouleur, et au final on arrive sur une couleur. Si la palette a été réduite, on a donc la couleur de remplacement. Mais si, lors du parcours, on ne trouve pas le fils correspondant, le chemin n'existe donc plus, et on va alors rechercher la couleur la plus proche parmi toutes les couleurs présentes dans l'arbre.

		\subsection{Méthodes de compression}

				\subsubsection{fusionCouleurs}
					Cette méthode prend un nœud en paramètre et fusionne ses fils. Pour ce faire, elle utilise moyenneListeColorsPonderation, à partir de la liste des OcTreeElement (couleur et nombre d'occurrences) des fils du nœud, pour calculer la couleur moyenne selon le nombre d'occurrences de chacune des couleurs. Puis on supprime le nœud pour le remplacer par le même contenant la nouvelle couleur grâce à colorMinDist de ColorEdit.

				\subsubsection{reductionPaletteParPourcentage}
					Prend en paramètre un pourcentage et fusionne les couleurs dont le pourcentage de présence est plus petit que celui donné en paramètre.
				Donc elle commence par récupérer toutes les sous-feuilles de l'arbre avec la somme des occurrences de leurs fils dans une liste triée par ce nombre. Puis pour chaque sous-feuille, elle vérifie si le pourcentage de la somme des occurrences est inférieur au paramètre, et dans ce cas, elle appelle fusionCouleurs. Sinon, elle ne fait rien.


		\section{ColorEditor}

			\subsection{Des distances}
				\subsubsection{distanceColors}
					Prend en paramètre deux couleurs, et en calcule la distance grâce à la formule de la plus variation monocomposante maximum, que nous avons choisie car le calcul de la composante la plus éloignée est intéressante dans le concept, et que le nom est sympa.

				\subsubsection{distance4Colors}
					Prend en paramètres quatre couleurs, et calcule la distance la plus grande entre toutes les couleurs, calculées grâce à distanceColors.

				\subsubsection{colorMinDist}
					Prend un Color et une liste d'OcTreeElement en paramètres pour trouver la distance minimale entre la couleur entrée en paramètre et chacune des couleurs de la liste. Cette distance est calculée avec distanceColors.
					Elle retourne la couleur la plus proche.

			\subsection{Des moyennes}
				\subsubsection{moyenneColors}
					Prend deux couleurs, et ressort une couleur composée de la moyenne de chaque composante.

				\subsubsection{moyenne4Colors}
					Fait la moyenne de quatre couleurs, grâce à moyenneColors.

				\subsubsection{moyenne2ColorsPonderation}
					Prend deux OcTreeElement, et ressort un OcTreeElement composé de la couleur moyenne pondérée de chaque composante et de la somme des occurrences de ces deux OcTreeElement.

				\subsubsection{moyenneListeColorsPonderation}
					Fait la moyenne d'une liste d'OcTreeElement grâce à moyenne2ColorsPonderation.
					
					
\section{Regrets}
	Avec plus de temps, nous aurions pu améliorer l'interactivité avec l'utilisateur, qu'il ait la possibilité de choisir plus de paramètres.
	Nous avions aussi pensé à une autre méthode de compression des OcTree : réduire la palette au nombre de couleurs choisi par l'utilisateur, mais nous ne l'avons finalement pas implantée.



	\chapter{Tests}
		\section{import d'une image dans le QuadTree}

			L'image importée est la suivante :

			\begin{figure}[h]
				\begin{center}
					\fbox{\includegraphics[width=3cm, height=4cm]{images/image_test.eps}}
				\end{center}
				\caption{Image $3\times 4$ pixels}
			\end{figure}

			Une fois importée, l'image se représente dans l'arbre comme le montre la Figure \ref{fig:apresimport}. Les feuilles contiennent les couleurs, non données ici :

			\begin{landscape}
				\begin{figure}

					\begin{center}
						\input{./arbres/arbre_apres_import.tex}
					\end{center}
					\caption{QuadTree de région}
					\label{fig:apresimport}
				\end{figure}
			\end{landscape}


		\section{compression}
			Après l'algorithme de compression, l'arbre ressemble à ceci :


			\begin{center}
				\input{./arbres/arbre_apres_compression.tex}
			\end{center}


			\vspace{0.5cm}On voit que les régions blanches ont été fusionnées.

		\section{import d'une image dans l'OcTree}

		En important la même image, comme on n'a que deux couleurs, on a donc deux feuilles. L'arbre obtenu est visualisé dans la Figure \ref{fig:octree}.

				\begin{figure}
					\begin{center}
						\input{./arbres/palette.tex}
					\end{center}
					\caption{OcTree}
					\label{fig:octree}
				\end{figure}

		\section{Tests de taux de compression}

			Nous avons testé avec l'image suivante :

				\begin{center}
					\includegraphics[width=3.5cm,height=3.6cm]{images/rtsr.eps}
				\end{center}
				\captionof{figure}{\label{fig:rosebase}Image de test}


			\subsection{Changement du taux de compression}

			\vspace{1cm}Des tests de différents taux de compression (au niveau du QuadTree) nous ont donné les résultats montrés dans la Figure \ref{fig:rose1}.


				\begin{center}
					\includegraphics[width=7.93cm,height=2.00cm]{images/sorties_dist.eps}
				\end{center}
				\captionof{figure}{\label{fig:rose1}Sorties}

				On voit bien ici la « pixellisation » de l'image au fur et à mesure qu'on augmente la distance de fusion.

			\subsection{Changement de la palette}

			Des tests de modifications de palettes se sont montrés moins concluants\dots{}  cf. Figure \ref{fig:rose2}

			\begin{center}
				\includegraphics[width=15.0cm,height=2.0cm]{images/sorties_per.eps}
				\captionof{figure}{Sorties 2}
				\label{fig:rose2}
			\end{center}

			Ici, la différence n'est franchement pas flagrante.
			

	\chapter*{Conclusion}

		Ce projet nous a fait découvrir le monde merveilleux de la compression d'images au format png, au moyen d'arbres. Nous avons pu mettre à l'épreuve la bibliothèque créée pendant la première partie du projet. Cela nous a permis de trouver et corriger les éventuelles erreurs que nous avions laissées. De plus, ce projet a permis d'occuper nos longues soirées d'automne, nous mettant à l'épreuve face aux rudesse du monde de java.

\end{document}
